#include "StdAfx.h"
#include "Algo.h"
#include <algorithm>
#include <map>

namespace algo1{


bool CalculateRouteCount_Step( std::vector<int>& vectNode, 
							   std::vector<CGraphBase::Edge>& vectScannedEdges, 
							   std::map<int, std::vector<Token>>& tokens,
							   std::vector<Event>& events,
							   CGraphBase& g )
{
	for( int k=0; k<vectNode.size();k++){
		TRACE("%d (%d)",vectNode[k], tokens[ vectNode[k] ].size() );
	}

	TRACE(" -> ");

	std::vector<int> vectTempNode = vectNode;

	for( int i=0; i<vectTempNode.size();i++){

		// check
		bool bCanGoNext = true;
		{
			for( int j=0; j<g._mapNodeInfo[ vectTempNode[i] ]._inputs.size();j++){
				int input = g._mapNodeInfo[ vectTempNode[i] ]._inputs[j];

				if( std::find( vectScannedEdges.begin(), vectScannedEdges.end(),CGraphBase::Edge( input, vectTempNode[i] ) ) ==
					vectScannedEdges.end() )
				{
					bCanGoNext = false;
					break;
				}
			}

			if( bCanGoNext == false )
			{
				continue;
			}
		}

		// go next
		{
			int nodeId = vectTempNode[i];

			// TODO: check ids
			bool bChanged = true; //false;
			{
				// TODO
			}

			if( !bChanged && g._mapNodeInfo[ nodeId ]._outputs.size() == g._mapNodeInfo[ nodeId ]._inputs.size() ) // one output?
			{
				// TODO
			}
			else if( g._mapNodeInfo[ nodeId ]._outputs.size() == 1 ) // one output?
			{
				int nextId = g._mapNodeInfo[ nodeId ]._outputs[0];

				//if( tokens.find( nextId ) == tokens.end() ){
				//	std::vector<Token> temp;
				//	tokens[ nextId ] = temp;
				//}

				for( int j=0; j< tokens[ nodeId ].size(); j++ ){
					tokens[ nextId ].push_back( tokens[ nodeId ][j] );
				}
			}
			else if( tokens[ nodeId ].size() == g._mapNodeInfo[ nodeId ]._outputs.size() )
			{
				for( int j=0; j<g._mapNodeInfo[ nodeId ]._outputs.size(); j++ )
				{
					tokens[ g._mapNodeInfo[ nodeId ]._outputs[j] ].push_back( tokens[nodeId][j] );
				}
			}
			else if( tokens[ nodeId ].size() < g._mapNodeInfo[ nodeId ]._outputs.size() )
			{
				// TODO
				std::vector<Token> vectOutputTokens = tokens[ nodeId ];

				while( vectOutputTokens.size() < g._mapNodeInfo[ nodeId ]._outputs.size() )
				{
					int oldSize = vectOutputTokens.size();

					for( std::vector<Token>::iterator itr = vectOutputTokens.begin(); 
						 itr != vectOutputTokens.end();
						 itr++ )
					{
						// break group
						if( itr->IsGroup() )
						{
							if( itr->subs.size() == 2 )
							{
								std::vector<Token>	subs = itr->subs;
								vectOutputTokens.erase( itr );

								vectOutputTokens.push_back( subs[0] );
								vectOutputTokens.push_back( subs[1] );

							}
							else
							{
								vectOutputTokens.push_back( itr->subs[ itr->subs.size()-1 ] );
								itr->subs.pop_back();
							}

							break;
						}
					}

					if( oldSize == vectOutputTokens.size() )
					{
						Event e;
						e._type = Event::CREATE;
						e._nodeId = nodeId;
						e._nodeTokens = tokens[ nodeId ];

						// if no group can be broken, create new
						int need = g._mapNodeInfo[ nodeId ]._outputs.size() - vectOutputTokens.size();
						for( int j=0; j<need; j++ )
						{
							Token t = Token::CreateToken();

							// TODO

							vectOutputTokens.push_back( t );
							e._createdTokens.push_back( t );
						}

						// TODO : set e._outputTokens and save it

						events.push_back( e );
					}
				}

				for( int j=0; j<g._mapNodeInfo[ nodeId ]._outputs.size(); j++ )
				{
					tokens[ g._mapNodeInfo[ nodeId ]._outputs[j] ].push_back( vectOutputTokens[j] );
				}


			}
			else if( tokens[ nodeId ].size() > g._mapNodeInfo[ nodeId ]._outputs.size() )
			{
				Event e;
				e._type = Event::GROUP;
				e._nodeId = nodeId;
				e._nodeTokens = tokens[ nodeId ];

				// TODO
				Token tGroup = Token::CreateToken();
				tGroup.group._nodeId = nodeId;
				tGroup.group._myCount = tokens[ nodeId ].size() - g._mapNodeInfo[ nodeId ]._outputs.size();
				tGroup.group._totalCount = tokens[ nodeId ].size();

				// add token
				std::vector<Token> vectOutputTokens;
				for( int j=0; j<tokens[ nodeId ].size(); j++ )
				{
					if( j < g._mapNodeInfo[ nodeId ]._outputs.size() -1 ){
						vectOutputTokens.push_back( tokens[ nodeId ][ j ] );
					}
					else{
						tGroup.subs.push_back( tokens[ nodeId ][ j ] );
					}
				}

				vectOutputTokens.push_back( tGroup );


				for( int j=0; j<g._mapNodeInfo[ nodeId ]._outputs.size(); j++ )
				{
					tokens[ g._mapNodeInfo[ nodeId ]._outputs[j] ].push_back( vectOutputTokens[j] );
				}

				// TODO : set e._outputTokens and save it
				events.push_back( e );

			}

			if( nodeId != g._lastNodeId ){
				tokens[ nodeId ].clear();
			}

			for( int j=0; j<g._mapNodeInfo[ vectTempNode[i] ]._outputs.size();j++){
				vectScannedEdges.push_back( CGraphBase::Edge( vectTempNode[i],g._mapNodeInfo[ vectTempNode[i] ]._outputs[j] ) );

				if( std::find( vectNode.begin(), vectNode.end(), g._mapNodeInfo[ vectTempNode[i] ]._outputs[j] ) ==
					vectNode.end() &&
					vectTempNode[i] != g._lastNodeId){
						vectNode.push_back(g._mapNodeInfo[ vectTempNode[i] ]._outputs[j]);
				}
			}

			vectNode.erase( std::find( vectNode.begin(), vectNode.end(), vectTempNode[i] ) );
		}
	}

	for( int k=0; k<vectNode.size();k++){
		TRACE("%d (%d)",vectNode[k], tokens[ vectNode[k] ].size() );
	}
	TRACE(" \n ");

	if( vectNode.size() == 0 )
		return true;

	return false;
}

void GetGroupedToken( Token t, std::vector<Token> & groupedToken )
{
	if( t.IsGroup() )
	{
		groupedToken.push_back( t );

		for( size_t i=0; i<t.subs.size(); i++ )
		{
			if( t.subs[i].IsGroup() )
			{
				GetGroupedToken( t.subs[i], groupedToken );
			}
		}
	}

}


int MaxSelection( std::vector< std::vector<int> > vectTokenSets, std::vector<int> vectRest )
{

	if( vectTokenSets.size() != vectRest.size() || vectTokenSets.size() == 0 )
	{
		return 0;
	}

	if( vectTokenSets.size() == 1 ){
		return ( vectRest[0] > vectTokenSets[0].size() ? vectRest[0] : vectTokenSets[0].size() );
	}

	if( vectTokenSets[ vectTokenSets.size()-1 ].size() == 0 || vectRest[vectRest.size() -1 ] == 0)
	{
		vectTokenSets.pop_back();
		vectRest.pop_back();
	}

	int max = 0;
	std::vector<int> vectTokens = vectTokenSets[ vectTokenSets.size()-1 ];
	for( size_t i=0; i<vectTokens.size(); i++ ){
		
		int token = vectTokens[i];
		std::vector< std::vector<int> > vectNewTokenSets = vectTokenSets;
		std::vector<int> vectNewRest = vectRest;

		// remove token
		for( size_t j=0; j<vectNewTokenSets.size(); j++ ){
			std::vector<int>::iterator itr = std::find( vectNewTokenSets[j].begin(), vectNewTokenSets[j].end(), token );

			if( itr != vectNewTokenSets[j].end() ){
				vectNewTokenSets[j].erase( itr );
			}
		}

		vectNewRest[ vectNewRest.size() - 1 ] = vectNewRest[ vectNewRest.size() - 1 ] - 1;

		int result = MaxSelection( vectNewTokenSets, vectNewRest ) + 1;

		if( max == 0 || result > max )
			max = result;
	}

	{
		std::vector< std::vector<int> > vectNewTokenSets = vectTokenSets;
		std::vector<int> vectNewRest = vectRest;

		vectNewRest[ vectNewRest.size() - 1 ] = vectNewRest[ vectNewRest.size() - 1 ] - 1;

		int result = MaxSelection( vectNewTokenSets, vectNewRest ) + 1;

		if( max == 0 || result > max )
			max = result;
	}

	return max;
};

int RouteCount( CGraphBase& g )
{
	std::vector<int> vectNode; 
	std::vector<CGraphBase::Edge> vectScannedEdges; 
	std::map<int, std::vector<Token>> tokens;
	std::vector<Event> events;
	
	TRACE("-------- RouteCount ----------\n");
	vectNode.push_back( g._firstNodeId );
	tokens[1].push_back( Token::CreateToken() );

	while( !CalculateRouteCount_Step( vectNode, vectScannedEdges, tokens, events, g ) )
	{}

	// --- analyze event to calculate route count ---
	std::vector<Token> groupedToken;

	std::vector< std::vector<int> > vectTokenSets;
	std::vector<int> vectRest;

	// 1. find grouped token
	for( size_t i=0; i<tokens[ g._lastNodeId ].size(); i++ ){
		GetGroupedToken( tokens[ g._lastNodeId ][i], groupedToken );
	}

	// 2. find related group event
	std::vector<Event> groupEvents;

	// search gropu token one by one
	for( size_t i=0; i<groupedToken.size(); i++ ){
		int nodeId = groupedToken[i].group._nodeId;
		
		std::vector<int> vectTokenSet;

		// find related group event
		for( size_t j=0; j<events.size(); j++ ){

			if( events[j]._type == Event::GROUP && events[j]._nodeId == nodeId ){
				groupEvents.push_back( events[j] );


				// find related create event
				for( size_t k=0; k< events[j]._nodeTokens.size(); k++ )
				{
					for( size_t l=0; l<events.size(); l++ ){

						if( events[l]._type == Event::CREATE && events[l]._nodeId >= nodeId ){

							// check if the CREATE EVENT's node includes the token.
							for( size_t m=0; m <events[l]._nodeTokens.size(); m++ )
							{
								if( events[l]._nodeTokens[m].uid == events[j]._nodeTokens[k].uid )
								{
									// add created token ids to vector for later use
									for( size_t n = 0; n < events[l]._createdTokens.size(); n++ )
									{
										vectTokenSet.push_back( events[l]._createdTokens[n].uid );
									}
									break;
								}
							}

						}
					}
				}

				break;
			}
		}

		// save token set and rest number
		vectTokenSets.push_back( vectTokenSet );
		vectRest.push_back( groupedToken[i].group._myCount );
	}

	// TODO 3. find related 
	int m = MaxSelection( vectTokenSets, vectRest );

	return -1;
}

}
